package com.atguigui.leetcode1;

import java.util.Arrays;

/**
 * 1326.灌溉花园的最少水龙头数目
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/2/21 8:59
 */
public class P1326MinimumNumberOfTapsToOpenToWaterAGarden {

    public static void main(String[] args) {
        Solution solution = new P1326MinimumNumberOfTapsToOpenToWaterAGarden().new Solution();
        // TO TEST
    }

    class Solution {
        int inf = (int) 1e5;

        public int minTaps(int n, int[] ranges) {
            int[] dp = new int[n + 1];
            Arrays.fill(dp, inf);
            dp[0] = 0;
            for (int i = 0; i <= n; i++) {
                int range = ranges[i];
                int l = i - range, r = i + range;
                int min = inf;
                for (int j = Math.max(l, 0); j <= Math.min(r, n); j++) {
                    min = Math.min(min, dp[j] + 1);
                }
                dp[Math.min(r, n)] = Math.min(dp[Math.min(r, n)], min);
            }

            return dp[n] == inf ? -1 : dp[n];
        }
    }
}
